package dynamicProgramming.r12_02;

import java.util.*;

public class Class322 {

    List<Integer> path = new ArrayList<Integer>();
    int min = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        if (amount < 0) {
            return -1;
        }
        Arrays.sort(coins);
        for (int i = 0, j = coins.length - 1; i < j; i++, j--) {
            int tmp = coins[i];
            coins[i] = coins[j];
            coins[j] = tmp;
        }
        backTracking(coins,amount,0);
        return min;

    }

    public void backTracking(int[] coins, int left, int start) {
        if (left == 0) {
            min = Math.min(min, path.size());
            return;
        }
        if (left<0){
            return;
        }
        for (int i = start; i < coins.length; i++) {
            left -= coins[i];
            path.add(coins[i]);
            backTracking(coins, left, start);
            path.remove(path.size() - 1);
            left += coins[i];
        }
    }



//TODO:2023/12/3 观看题解
    class Solution {

        //TODO:2023/12/3 递归 和我上面的回溯法 几乎一样 的思路 都是面临着超时的问题
        int res = Integer.MAX_VALUE;
        public int coinChange(int[] coins, int amount) {
            if(coins.length == 0){
                return -1;
            }
            findWay(coins,amount,0);
            // 如果没有任何一种硬币组合能组成总金额，返回 -1。
            if(res == Integer.MAX_VALUE){
                return -1;
            }
            return res;
        }


        public void findWay(int[] coins,int amount,int count){
            if(amount < 0){
                return;
            }
            if(amount == 0){
                res = Math.min(res,count);
            }
            for(int i = 0;i < coins.length;i++){
                findWay(coins,amount-coins[i],count+1);
            }
        }


        //TODO:2023/12/3  进阶 带有备忘录

    int[] memo;
    public int coinChange1(int[] coins, int amount) {
        if(coins.length == 0){
            return -1;
        }
        memo = new int[amount];

        return findWay(coins,amount);
    }
    // memo[n] 表示钱币n可以被换取的最少的硬币数，不能换取就为-1
    // findWay函数的目的是为了找到 amount数量的零钱可以兑换的最少硬币数量，返回其值int
    public int findWay(int[] coins,int amount){
        if(amount < 0){
            return -1;
        }
        if(amount == 0){
            return 0;
        }
        // 记忆化的处理，memo[n]用赋予了值，就不用继续下面的循环
        // 直接的返回memo[n] 的最优值
        if(memo[amount-1] != 0){
            return memo[amount-1];
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0;i < coins.length;i++){
            int res = findWay(coins,amount-coins[i]);
            if(res >= 0 && res < min){
                min = res + 1; // 加1，是为了加上得到res结果的那个步骤中，兑换的一个硬币
            }
        }
        memo[amount-1] = (min == Integer.MAX_VALUE ? -1 : min);
        return memo[amount-1];
    }


//TODO:2023/12/3  动态规划
    public int coinChange2(int[] coins, int amount) {
        // 自底向上的动态规划
        if(coins.length == 0){
            return -1;
        }

        // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
        int[] memo = new int[amount+1];
        // 给memo赋初值，最多的硬币数就是全部使用面值1的硬币进行换
        // amount + 1 是不可能达到的换取数量，于是使用其进行填充
        Arrays.fill(memo,amount+1);
        memo[0] = 0;
        for(int i = 1; i <= amount;i++){
            for(int j = 0;j < coins.length;j++){
                if(i - coins[j] >= 0){
                    // memo[i]有两种实现的方式，
                    // 一种是包含当前的coins[i],那么剩余钱就是 i-coins[i],这种操作要兑换的硬币数是 memo[i-coins[j]] + 1
                    // 另一种就是不包含，要兑换的硬币数是memo[i]
                    memo[i] = Math.min(memo[i],memo[i-coins[j]] + 1);
                }
            }
        }

        return memo[amount] == (amount+1) ? -1 : memo[amount];
    }








    }



    public static void main(String[] args) {
        Class322 class322 = new Class322();
        int[] nums={1, 2, 5};

        Solution solution = new Class322().new Solution();
        System.out.println(solution.coinChange2(nums,11));

    }
}



